/***尚硅谷Java数据结构与java算法                 ***/
/***https://www.bilibili.com/video/BV1E4411H73v***/
/***kmp算法             P155                   ***/
/***C++ 实现版本    written by Daniel           ***/

#include <string>
#include <iostream>
#include <vector>

using std::string;
using std::cout;
using std::endl;
using std::vector;

class Kmp
{
public:
    //构造函数传入两个字符串  总字符串和子字符串
    //第一个为总字符串，第二个为模式字符串  
    Kmp(const string& oriStr,const string& partStr):oriStr(oriStr),partStr(partStr),kmpNext(partStr.length(),0)
    {  }
    /*
    功能：暴力匹配方法
    参数：无
    返回值：字符串匹配的第一个位置，若无匹配，返回-1    
    */
    int strMatch()
    {
        /*暴力解法*/
        //i和j分别指向全串和模式串
        size_t i=0, j=0;
        if (oriStr.length()<partStr.length())
            return -1;
        auto size=oriStr.length()-partStr.length()+1;
        for (;i<size;i++)
        {
            while (j<partStr.length() && oriStr[i+j]==partStr[j])
            {
                j++;
            }
            if (j==partStr.length()){
                return i;
            }        
            j=0;
        }
        return -1;
    }

    int kmpMatch()
    {
        /*kmp解法*/
        //i和j分别指向全串和模式串
        int i=0, j=0;
        if (oriStr.length()<partStr.length())
            return -1;
        auto size=oriStr.length()-partStr.length()+1;
        for (;i<size;i++)
        {
            while (j<partStr.length() && oriStr[i+j]==partStr[j])
            {
                j++;
            }
            if (j==partStr.length()){
                return i;
            }        
            //当发生不匹配的时候，调整模式串的位置即可
            else{
                //模式串指针的位置
                j=kmpNext[j-1];
                i+=(j-kmpNext[j-1]);
            }
        }
        return -1;
    }

    /*
    功能：求解模式串的每一段的最长前后缀；
    参数：空，存储在全局参数中
    返回值：空， 存储在类的全局参数中
    */
    void generateKmpNext()
    {
        kmpNext[0]=0;
        size_t i=1,j=0;
        auto length=partStr.length();
        //i是 代表第i个字符  j代表，前一个字符串的  最长公共前后缀的长度
        while (i<length)
        {
            if (partStr[i]==partStr[j]){
                kmpNext[i++]=++j;
            }
            else{
                if (j==0){
                    kmpNext[i++]=j;
                    continue;
                }
                j=kmpNext[j-1];
            }
        }
        
    }
    void printNext()
    {
        for(const auto& item:kmpNext){
            cout<<item<<"\t";
        }
        cout<<endl;
    }

private:
    string oriStr;
    string partStr;
    vector<int> kmpNext;
};

int main()
{
    string oriStr="bbc abcdab abcdabcdabde";
    string partStr="abbabbaaabbb";
    Kmp kmp(oriStr,partStr);
    kmp.generateKmpNext();
    kmp.printNext();
    cout<<kmp.strMatch()<<endl;
    cout<<kmp.kmpMatch()<<endl;
}